/* ******************************************************************************
 *  ENGINE.HH
 * ******************************************************************************/

/* *
 * Copyright (C) 2005 Atul S. Vasu
 *
 * This program is free software; you cn redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 * */

/* *
 * Contact Details:
 *
 * mail
 *  Atul S. Vasu, Flat No. 3, Govt Quarters, Kowdiar,
 *  Thiruvananthapuram, Kerala, India. 695003.
 * email
 *        - atulsvasu@gmail.com
 *        - atulsv@cse.iitm.ernet.in (till early 2007).
 * */

//
// TODO
//  * Implement 50 move rule.(No pawn move or capture within last 50 moves is a draw)
//  * Implement Three Fold repetition draw & perpetual check draw.
//  * Implement ``Insufficient material to mate''  draw.
//

#ifndef __ENGINE_H_
#define __ENGINE_H_

#ifndef _SINGLE_
#include <iostream>
#include <list>
#include <algorithm>
#endif

#include"board.h"

/// Move
/**
 * Describes a move completely. It encompases all kinds
 * of moves. Including promotion, castle, en-passant etc.
 * Standard way of storing castle is the corresponding
 * King's movement. And the way of storing promotion is
 * to have the promote as the piece to be promoted.
 * It is required that the promote should also be of same
 * colour(Obviously). If it is not a promotion value of
 * promote is undefined. With the exception that it may
 * may be considered to be EMPTY if stored in ML. This
 * for distinguishing easily from a promotion, for displaying
 * purposes.
 */
struct move {
  cell from,to; ///< Move the piece @ from 2 to!
  piece promote;///< If it is a pawn promotion promote to promote!

  move(const cell& f, const cell& t):from(f),to(t),promote(EMPTY) {}
  move(const move& m):from(m.from),to(m.to),promote(m.promote) {}
  /// Convert string representation to move.
  /**
   * Representation is like e2e4 or b7c8q etc.
   * It is usually read from user and passed to constructor for parsing.
   */
  move(std::string& str, colour c):from(OUT), to(OUT),promote(EMPTY) {
    if(str.length()>=4) {
      from = (str[0]-'a')+(str[1]-'1')*n;
      to=(str[2]-'a')+(str[3]-'1')*n;
      if(str.length()>4)
	switch(str[str.length()-1]) {
	case 'P': case 'p': if(c==WHITE) promote=WPAWN;  else promote=BPAWN; break;
	case 'B': case 'b': if(c==WHITE) promote=WBISHOP; else promote=BBISHOP; break;
	case 'N': case 'n': if(c==WHITE) promote=WKNIGHT; else promote=BKNIGHT; break;
	case 'R': case 'r': if(c==WHITE) promote=WROOK; else promote=BROOK; break;
	case 'Q': case 'q': if(c==WHITE) promote=WQUEEN; else promote=BQUEEN; break;
	case 'K': case 'k': if(c==WHITE) promote=WKING; else promote=BKING; break;
	default: promote=EMPTY; break;
	}
      else
	promote=EMPTY;
    }else
      promote=EMPTY;
  }
  move& operator = (const move& M) {
    from=M.from; to=M.to; promote=M.promote;
    return *this;
  }
} nullMove(A1,A1), placeHolder(B1, B1);
bool operator == (const move& m1, const move& m2) {
  return m1.from==m2.from and m1.to==m2.to and m1.promote==m2.promote;
}
bool operator != (const move& m1, const move& m2) {
  return m1.from!=m2.from or m1.to!=m2.to or m1.promote!=m2.promote;
}

std::ostream& operator << (std::ostream& os, const move& m) {
  os <<char('a'+FILE(m.from))<<char('1'+RANK(m.from))
	    <<char('a'+FILE(m.to))<<char('1'+RANK(m.to));
  if(m.promote!=EMPTY) {
    switch(m.promote) {
    case EMPTY: break;//Unreachable code.
    case WPAWN:   os<<'='<<'p'; break;
    case WBISHOP: os<<'='<<'b'; break;
    case WKNIGHT: os<<'='<<'n'; break;
    case WROOK:   os<<'='<<'r'; break;
    case WQUEEN:  os<<'='<<'q'; break;
    case WKING:   os<<'='<<'k'<<"!?"; break;
    case BPAWN:   os<<'='<<'p'; break;
    case BBISHOP: os<<'='<<'b'; break;
    case BKNIGHT: os<<'='<<'n'; break;
    case BROOK:   os<<'='<<'r'; break;
    case BQUEEN:  os<<'='<<'q'; break;
    case BKING:   os<<'='<<'k'<<"!?"; break;
    default:      os<<'='<<'?'; break;
    }
  }
  return os;
}


/// Move-List
/**
 * It can be used for many purposes. It can be used to store the
 * history of moves played. It can be used to store all the
 * moves at a position. It can be used to store the set of
 * validated moves, etc.
 *
 * It is chosen to be double-linked list despite the necessity to
 * sort for the purpose of move-ordering. This is due to many
 * reasons. First the number of moves is highly uncertain at every
 * position. Secondly many of the moves may be invalid, as they
 * may open king to a check, so it should removed. Removing intermediate
 * values in a vector is time consuming. And an algorithm for
 * sorting linked-list is avalaible with a decent efficiency.
 */

typedef std::list<move> move_list;

/// Differences due to a move.
/**
 * It stores the set of differences in the position due to some
 * particular move. It is used for undoing the move. It removes
 * the necessity of the storing the whole board for undoing
 * purposes. It should be very efficient to use delta rather than
 * copying the entire board.
 *
 * The notion of simple-delta, ie. moves which affect nothing
 * other than two squares, may be dealt seperately. But to reduce
 * this effect, the size of aux_info was made tremendously small
 * as 5 bytes and two comparisons is not costly. If I use a simple
 * delta mechanism it will require 1 or 3 comparisons and if I used
 * a big aux_info copying of large 20-byte information. Further to
 * optimize I would have to use uninitalised constructor for simple
 * deltas. Another major reason to avoid simple-delta mechanism is
 * it is too complex!! (I have implemented it and became mad).
 *
 * c1 and c2 will be always valid!
 * c3 and c4 may or may not be valid, signalled by OUT.
 * If c3 or c4 is invalid the corresponding p3, p4 has some
 * undefined value.
 *
 * A is the old aux_info of the board.
 */
struct delta {
  cell c1,c2,c3,c4;///< Cells which affected.
  piece p1,p2,p3,p4; ///< Pieces which were there earlier.
  aux_info A;///< Old aux_info.

  delta(const aux_info& aa, const cell& cc1, const cell& cc2,
    const piece& pp1, const piece& pp2):
    c1(cc1),c2(cc2),c3(OUT),c4(OUT),p1(pp1),p2(pp2),p3(EMPTY),p4(EMPTY),A(aa) {}
};
/// Delta-List
/**
 * Used for storing the table of delta's. This is may be
 * a stack or a vector. It is still under consideration.
 * It is used to keep track of the history completely.
 */
typedef std::list<delta> delta_list;

/// The Game Engine.
/**
 * Every move/ action takes place here.
 * It keeps tracks of moves/deltas etc.
 * It can be printed to show the board.
 * It has a move-generator, validity checker etc.
 */
class engine {
public:
  /// Stores the current position.
  /**
   * P completely specifies the positional information.
   *
   */
  position P;
  /// ML stores the list of moves played
  /**
   * Principally used for opening book particulars and
   * for displaying the movelist in the interface.
   */
  move_list ML;
private:
  /// history of changes.
  /**
   * Used for undo-ing the moves played.Undoing before
   * first move has no effect. But don't assume on that.
   * It may be removed for performance.
   */
  delta_list history;

  //NOTE: number of moves played can be obtained
  // either from history.size() or ML.size(), hence
  // an additional variable to store it is not
  // considered. Further it is almost never used.
#define HV_ATTACK(p) (p==WROOK or p==WQUEEN or p==BROOK or p==BQUEEN)
#define DI_ATTACK(p) (p==WBISHOP or p==WQUEEN or p==BBISHOP or p==BQUEEN)

  bool trace(cell c, int dF, int dR, colour hostile) const{
    int diff=n*dR+dF;
    cell t(c+diff);
    int f(FILE(c)+dF), r(RANK(c)+dR);

    int hv=false;
    if(std::abs(dF)+std::abs(dR)==1)
      hv=true;

    piece att;
    for( ; 0<=f and f<n and 0<=r and r<n; f+=dF, r+=dR,t+=diff)
      if((att=P.CB[t])!=EMPTY)  {
	if(hv) {
	  if(HV_ATTACK(att) and colour_of(att)==hostile)
	    return true;
	}else {
	  if(DI_ATTACK(att) and colour_of(att)==hostile)
	    return true;
	}
	break;
      }

    return false;
  }
  bool strace(cell c, int dF, int dR, colour hostile, piece p1, piece p2) const{
    int diff=n*dR+dF;
    cell t(c+diff);
    int f(FILE(c)+dF), r(RANK(c)+dR);

    if(0<=f and f<n and 0<=r and r<n) {
      piece att=P.CB[t];
      if((att==p1 or att==p2) and colour_of(att)==hostile)
	return true;
    }
    return false;
  }


  /// Checks whether cell c is under threat by `by'
  /**
   * It assumes that c is a KING,or atleast not a pawn.
   * This is to avoid checking the en-passant capture.
   * We use this function only to check whether the KING is
   * open to attack to validate moves. But as a bye-product
   * we get a more usefull function, which may be used for
   * evaluation purposes.
   *
   * Written as a big & complex function, because this check will
   * be done after each move-generation, making move-generation slower.
   * So it should be extremely quick!
   */

  bool under_threat(const cell& c, const colour& by) const{
    if(trace(c,-1,-1,by)) return true;
    if(trace(c,-1, 0,by)) return true;
    if(trace(c,-1,+1,by)) return true;
    if(trace(c, 0,-1,by)) return true;
    if(trace(c, 0,+1,by)) return true;
    if(trace(c,+1,-1,by)) return true;
    if(trace(c,+1, 0,by)) return true;
    if(trace(c,+1,+1,by)) return true;

    if(strace(c,-2,-1,by,BKNIGHT,WKNIGHT)) return true;
    if(strace(c,-2,+1,by,BKNIGHT,WKNIGHT)) return true;
    if(strace(c,-1,-2,by,BKNIGHT,WKNIGHT)) return true;
    if(strace(c,-1,+2,by,BKNIGHT,WKNIGHT)) return true;
    if(strace(c,+1,-2,by,BKNIGHT,WKNIGHT)) return true;
    if(strace(c,+1,+2,by,BKNIGHT,WKNIGHT)) return true;
    if(strace(c,+2,-1,by,BKNIGHT,WKNIGHT)) return true;
    if(strace(c,+2,+1,by,BKNIGHT,WKNIGHT)) return true;

    if(strace(c,-1,-1,by,BKING,WKING)) return true;
    if(strace(c,-1, 0,by,BKING,WKING)) return true;
    if(strace(c,-1,+1,by,BKING,WKING)) return true;
    if(strace(c, 0,-1,by,BKING,WKING)) return true;
    if(strace(c, 0,+1,by,BKING,WKING)) return true;
    if(strace(c,+1,-1,by,BKING,WKING)) return true;
    if(strace(c,+1, 0,by,BKING,WKING)) return true;
    if(strace(c,+1,+1,by,BKING,WKING)) return true;

    // PAWN attacks.
    if(by==WHITE){
      if(RANK(c)!=0) {
	if(FILE(c)!=n-1)
	  if(P.CB[c-(n-1)]==WPAWN)
	    return true;
	if(FILE(c)!=0)
	  if(P.CB[c-(n+1)]==WPAWN)
	    return true;
      }
    }
    else{
	if(RANK(c)!=n-1) {
	  if(FILE(c)!=0)
	    if(P.CB[c+(n-1)]==BPAWN)
	      return true;	
	  if(FILE(c)!=n-1)
	    if(P.CB[c+(n+1)]==BPAWN)
	      return true;
	}
    }

    // I think nothing is left.
    return false;
  }
  /// Checks whether the move m opens the friendly king to check
  /**
   * It is for validating a normal move.
   */
  bool opens_king(const move& m) const {
    return const_cast<engine*>(this)->opens_king(m);
  }

private:
  bool opens_king(const move& m) {
    //It is very difficult to do this, efficiently & in const environment.
    // We shall do in non-const environment and do it with reasonable efficiency.
    bool opens;
    make_move(m);
    opens = (P.A.to_move==WHITE)?under_threat(P.A.bk_pos,WHITE):under_threat(P.A.wk_pos,BLACK);
    undo_move();
    return opens;
  }
public:
  /// Add all promoting moves
  /**
   * A simple helper function. Ideal if inlined.
   * FIXME, there is some bug here, I am unable to catch it.
   */
  void add_promotion(move M, move_list& l) const{
    if(P.A.to_move==WHITE) {
      M.promote=WQUEEN; l.push_back(M);
      M.promote=WKNIGHT; l.push_back(M);
      M.promote=WROOK; l.push_back(M);
      M.promote=WBISHOP; l.push_back(M);
    } else {
      M.promote=BQUEEN; l.push_back(M);
      M.promote=BKNIGHT; l.push_back(M);
      M.promote=BROOK; l.push_back(M);
      M.promote=BBISHOP; l.push_back(M);
    }
  }
  /// Long - Move generator
  /**
   * c - from where move is initiated.
   * dR - change in Rank by one step.
   * dF - change in File by one step.
   * hostile - hostile colour, that can be captured.
   * l  - move-list to which the moves generated will be appended.
   *
   * Some one should consider rewritting the code by some thing more efficient.
   *
   */
  void long_move(cell c, int dR, int dF, colour hostile, move_list& l) const{
    int diff=n*dR+dF;// The change it causes to c.
    int r=RANK(c)+dR, f=FILE(c)+dF;
    move M(c,c+diff);
    // Pretty costly implementation. Can be improved
    // at the expense of long codes.
    // There are 3^2 = 9 possibilites and all may be implemented seperately
    // The case when both are zero is assumed not to occur.
    for(;0<=r and r<n and 0<=f and f<n; r+=dR, f+=dF,M.to+=diff)
      {
	piece q(P.CB[M.to]);
	if(q!=EMPTY)
	  {
	    if(colour_of(q)==hostile)
	      l.push_back(M);
	    break;
	  }
	l.push_back(M);
      }
  }
  /// Short move generator
  /**
   * Attempt move from c to c+i.dF+j.dR in vector form!
   */
  void short_move(cell c, int dR, int dF, colour self, move_list& l) const{
    int r(RANK(c)+dR),f(FILE(c)+dF);
    move M(c,c+n*dR+dF);
    if(0<=r and r<n and 0<=f and f<n)
	if(colour_of(P.CB[M.to])!=self)
	  l.push_back(M);
  }

  void smoves_to(cell c, int dR, int dF, colour self, move_list& l) const{
    int r(RANK(c)+dR),f(FILE(c)+dF);
    move M(c+n*dR+dF,c);
    if(0<=r and r<n and 0<=f and f<n)
	if(colour_of(P.CB[M.from])==P.A.to_move)
	  l.push_back(M);
  }
  void moves_to(cell c, int dR, int dF, colour self, const bool accessList[13], move_list &l) const{
		       /*e, p, b, n, r, q, k, p, b, n, r, q, k*/
    const bool slow[]= { 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1}; 	
    //Take special care for pawn.
    int diff=n*dR+dF;// The change it causes to c.
    int r=RANK(c)+dR, f=FILE(c)+dF;
    move M(c+diff,c);
    int i=1;

    for(;0<=r and r<n and 0<=f and f<n; r+=dR, f+=dF,M.from+=diff,++i)
      {
	piece q(P.CB[M.from]);
	if(colour_of(q)==P.A.to_move)
	  {
	    if(slow[q]) {
	      if(i==1) {
	        if(q==WPAWN || q==BPAWN) {
		  if( (self==NONE && dR==0) || (self!=NONE && dF==0)) {
		    l.push_back(M);	
		  }
		} else
		  l.push_back(M);		
	      }		
	    }else
	      l.push_back(M);
	    break;
	  }
      }

  }

  /// Adds to list l the moves to cell c.
  /**
   *
   */
  void get_moves_to(cell c, move_list& l) const {
	  //TODO en-passant & castling...
    piece p (P.CB[c]);
    colour self=colour_of(p);
    if(self==P.A.to_move)
      return ;
		                 /*e, p, b, n, r, q, k, p, b, n, r, q, k*/
    const bool accessList1[13] = { 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1};
    const bool accessList2[13] = { 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1};
    const bool accessList3[13] = { 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1};
    const bool accessList4[13] = { 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1};
    const bool accessList5[13] = { 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1};
    const bool accessList6[13] = { 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1};
    const bool accessList7[13] = { 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1};
    const bool accessList8[13] = { 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1};

    moves_to(c,+1, 0,self, accessList1,l);
    moves_to(c,-1, 0,self, accessList2,l);
    moves_to(c, 0,+1,self, accessList3,l);
    moves_to(c, 0,-1,self, accessList4,l);
    moves_to(c,+1,+1,self, accessList5,l);
    moves_to(c,+1,-1,self, accessList6,l);
    moves_to(c,-1,+1,self, accessList7,l);
    moves_to(c,-1,-1,self, accessList8,l);
    smoves_to(c,+1,+2,self, l);
    smoves_to(c,+1,-2,self, l);
    smoves_to(c,-1,+2,self, l);
    smoves_to(c,-1,-2,self, l);
    smoves_to(c,+2,+1,self, l);
    smoves_to(c,+2,-1,self, l);
    smoves_to(c,-2,+1,self, l);
    smoves_to(c,-2,-1,self, l);
  }


  /// Adds to list l the moves of at cell c.
  /**
   * It first verifies that the piece at cell c is of the colour which should play the next.
   * Generates all possible moves of that piece and push_backs them to l.
   */
  void get_moves_of(cell c, move_list& l) const{
    piece p (P.CB[c]);
    if(colour_of(p)!=P.A.to_move)
      return ;
    move M(c,OUT);

    switch(p)
      {
      case EMPTY: return ; // Unreachable
      case WPAWN:
	// A pawn is never on 7th rank, hence it can always be moved forward.
	if(RANK(c)==n-2) {
	  //All moves are promotions.
	  M.to=c+n;
	  if(P.CB[M.to]==EMPTY)
	    add_promotion(M,l);
	  M.to=c+(n-1);
	  if(FILE(c)!=0)
	    if(colour_of(P.CB[M.to])==BLACK)
	      add_promotion(M,l);
	  M.to=c+(n+1);
	  if(FILE(c)!=n-1)
	    if(colour_of(P.CB[M.to])==BLACK)
	      add_promotion(M,l);
	} else {
	  M.to=c+n;
	  if(P.CB[M.to]==EMPTY) {
	    l.push_back(M);
	    if(RANK(c)==1) {
	      M.to=M.to+n;
	      if(P.CB[M.to]==EMPTY)
		l.push_back(M);
	    }
	  }

	  M.to=c+(n-1);
	  if(FILE(c)!=0)
	    if(colour_of(P.CB[M.to])==BLACK or M.to==P.A.eps_b)
	      l.push_back(M);
	  M.to=c+(n+1);
	  if(FILE(c)!=n-1)
	    if(colour_of(P.CB[M.to])==BLACK or M.to==P.A.eps_b)
	      l.push_back(M);
	}
	break;
      case WBISHOP:
	long_move(c,-1,-1,BLACK,l);	long_move(c,-1,+1,BLACK,l);
	long_move(c,+1,-1,BLACK,l);	long_move(c,+1,+1,BLACK,l);
	break;
      case WKNIGHT:
	short_move(c,-2,-1,WHITE,l);	short_move(c,-2,+1,WHITE,l);
	short_move(c,-1,-2,WHITE,l);	short_move(c,-1,+2,WHITE,l);
	short_move(c,+1,-2,WHITE,l);	short_move(c,+1,+2,WHITE,l);
	short_move(c,+2,-1,WHITE,l);	short_move(c,+2,+1,WHITE,l);
	break;
      case WROOK:
	long_move(c,-1, 0,BLACK,l);	long_move(c,+1, 0,BLACK,l);
	long_move(c, 0,-1,BLACK,l);     long_move(c, 0,+1,BLACK,l);
	break;
      case WQUEEN:
	long_move(c,-1,-1,BLACK,l);	long_move(c,-1,+1,BLACK,l);
	long_move(c,+1,-1,BLACK,l);	long_move(c,+1,+1,BLACK,l);
	long_move(c,-1, 0,BLACK,l);	long_move(c,+1, 0,BLACK,l);
	long_move(c, 0,-1,BLACK,l);     long_move(c, 0,+1,BLACK,l);
	break;
      case WKING:
	short_move(c,-1,-1,WHITE,l);	short_move(c,-1,+1,WHITE,l);
	short_move(c,+1,-1,WHITE,l);	short_move(c,+1,+1,WHITE,l);
	short_move(c,-1, 0,WHITE,l);	short_move(c,+1, 0,WHITE,l);
	short_move(c, 0,-1,WHITE,l);    short_move(c, 0,+1,WHITE,l);
	
	// Short Castle
	//  position should be E1=[K] [.] [.] [R],
	//  and none-of-them K,R has moved earlier
	//  It should it pass through squares under attack.
	//  This includes E1, F1 and G1. But G1 may be removed
	// because it would be immediately checked for validation!.
	{
	  bool valid=false,check=false;
	  //Technique to avoid calling under_theat minimal number of types.
	
	  if(P.A.short_w and P.CB[F1]==EMPTY and P.CB[G1]==EMPTY) {
	    valid=true; check=under_threat(E1,BLACK);
	    if(not check)
	      if(not under_threat(F1,BLACK))
	      { M.to=G1; l.push_back(M);}
	  }
	  // Long castle rules are similar to short castle.
	  if(P.A.long_w and P.CB[D1]==EMPTY and P.CB[C1]==EMPTY and P.CB[B1]==EMPTY) {
	    if(not valid)
	      check=under_threat(E1,BLACK);
	    if(not check)
	      if(not under_threat(D1,BLACK))
		{ M.to=C1; l.push_back(M);}
	  }
	}
	break;
      case BPAWN:
	if(RANK(c)==1) {
	  //All moves are promotions.
	  M.to=c-n;
	  if(P.CB[M.to]==EMPTY)
	    add_promotion(M,l);
	  M.to=c-(n+1);
	  if(FILE(c)!=0)
	    if(colour_of(P.CB[M.to])==WHITE)
	      add_promotion(M,l);
	  M.to=c-(n-1);
	  if(FILE(c)!=n-1)
	    if(colour_of(P.CB[M.to])==WHITE)
	      add_promotion(M,l);
	} else {
	  M.to=c-n;
	  if(P.CB[M.to]==EMPTY) {
	    l.push_back(M);
	    if(RANK(c)==n-2) {
	      M.to=M.to-n;
	      if(P.CB[M.to]==EMPTY)
		l.push_back(M);
	    }
	  }

	  M.to=c-(n+1);
	  if(FILE(c)!=0)
	    if(colour_of(P.CB[M.to])==WHITE or M.to==P.A.eps_w)
	      l.push_back(M);
	  M.to=c-(n-1);
	  if(FILE(c)!=n-1)
	    if(colour_of(P.CB[M.to])==WHITE or M.to==P.A.eps_w)
	      l.push_back(M);
	}
	break;	
      case BBISHOP:
	long_move(c,-1,-1,WHITE,l);	long_move(c,-1,+1,WHITE,l);
	long_move(c,+1,-1,WHITE,l);	long_move(c,+1,+1,WHITE,l);
	break;
      case BKNIGHT:
	short_move(c,-2,-1,BLACK,l);	short_move(c,-2,+1,BLACK,l);
	short_move(c,-1,-2,BLACK,l);	short_move(c,-1,+2,BLACK,l);
	short_move(c,+1,-2,BLACK,l);	short_move(c,+1,+2,BLACK,l);
	short_move(c,+2,-1,BLACK,l);	short_move(c,+2,+1,BLACK,l);
	break;
      case BROOK:
	long_move(c,-1, 0,WHITE,l);	long_move(c,+1, 0,WHITE,l);
	long_move(c, 0,-1,WHITE,l);     long_move(c, 0,+1,WHITE,l);
	break;
      case BQUEEN:
	long_move(c,-1,-1,WHITE,l);	long_move(c,-1,+1,WHITE,l);
	long_move(c,+1,-1,WHITE,l);	long_move(c,+1,+1,WHITE,l);
	long_move(c,-1, 0,WHITE,l);	long_move(c,+1, 0,WHITE,l);
	long_move(c, 0,-1,WHITE,l);     long_move(c, 0,+1,WHITE,l);
	break;
      case BKING:
	short_move(c,-1,-1,BLACK,l);	short_move(c,-1,+1,BLACK,l);
	short_move(c,+1,-1,BLACK,l);	short_move(c,+1,+1,BLACK,l);
	short_move(c,-1, 0,BLACK,l);	short_move(c,+1, 0,BLACK,l);
	short_move(c, 0,-1,BLACK,l);    short_move(c, 0,+1,BLACK,l);

	// Short Castle
	//  position should be E8=[K] [.] [.] [R],
	//  and none-of-them K,R has moved earlier
	//  It should it pass through squares under attack.
	//  This includes E8, F8 and G8. But G8 may be removed
	// because it would be immediately checked for validation!.
	{
	  bool valid=false,check=false;
	  //Technique to avoid calling under_theat minimal number of types.
	  if(P.A.short_b and P.CB[F8]==EMPTY and P.CB[G8]==EMPTY) {
	    valid=true; check=under_threat(E8,WHITE);
	    if(not check)
	      if(not under_threat(F8,WHITE))
		{ M.to=G8; l.push_back(M); }
	  }
	  // Long castle rules are similar to short castle.
	  if(P.A.long_b and P.CB[D8]==EMPTY and P.CB[C8]==EMPTY and P.CB[B8]==EMPTY) {
	    if(not valid)
	      check=under_threat(E8,WHITE);
	    if(not check)
	      if(not under_threat(D8,WHITE))
	      {M.to=C8; l.push_back(M);}
	  }
	}
	break;
      default: return; // Unreachable - assert.
      }
  }
  /// Validates a list of moves.
  /**
   * Assumes that the move is partially valid, i.e. it is something
   * generated by the get_moves function.
   */
  void validate(move_list& l) {
    move_list::iterator first(l.begin()), last(l.end());
    while(first!=last)
      if(opens_king(*first))
	first=l.erase(first);
      else
	++first;
  }
public:
  /// Default Constructor.
  engine():P(),ML(),history() {}
  /// Copy Constructor.
  engine(const engine& e):P(e.P),ML(e.ML),history(e.history) {}
  /// Destructor.
  ~engine() {}
  /// Whether under check?
  /**
   * -Usefull- for seeing who wins/lose at the end.
   */
  bool under_check() {
    if(P.A.to_move==WHITE)
      return under_threat(P.A.wk_pos,BLACK);
    else
      return under_threat(P.A.bk_pos,WHITE);
  }
  /// Is there a pawn at 7th rank.
  /**
   * Used for search extension by step 1.
   * So only a pawn for the player who should make the move is considered.
   */
  bool pawn_7() {
    if(P.A.to_move==WHITE) {
      return P.CB[A7]==WPAWN or P.CB[B7]==WPAWN or P.CB[C7]==WPAWN or P.CB[D7]==WPAWN or P.CB[E7]==WPAWN or P.CB[F7]==WPAWN
	or P.CB[G7]==WPAWN or P.CB[H7]==WPAWN;
    }else {
      return P.CB[A2]==BPAWN or P.CB[B2]==BPAWN or P.CB[C2]==BPAWN or P.CB[D2]==BPAWN or P.CB[E2]==BPAWN or P.CB[F2]==BPAWN
	or P.CB[G2]==BPAWN or P.CB[H2]==BPAWN;
    }
  }
  /// Whether last move is a capture.
  /**
   *
   */
  bool l_capture() {
    if(history.empty()) return false;
    delta d=history.back();
    if(d.p2!=EMPTY)
      return true;
    else
      return false;
  }

  /// Reset the engine
  /**
   * Refresh the entries to the beginning situation.
   */
  void reset() {
    P.reset();
    ML.clear();
    history.clear();
  }
  /// Returns the number of moves
  /**
   * For the purpose of use with XBoard/Interface.
   */
  int no_of_moves() {
    return (ML.size()+1)/2;
  }

  /// Make the move m.
  /**
   * It doesn't check the validity of the move. Not even
   * bound-checking. It is assumed true, for maximum performace.
   * If the move is entired by the user, one may use the is_valid
   * first to check it before using make_move. The behaviour is
   * undefined (possibly catastrophic) for invalid moves.
   */
  void make_move(const move& m) {
    ML.push_back(m);
    delta d(P.A,m.from,m.to,P.CB[m.from],P.CB[m.to]);

    P.CB[m.to]=d.p1;
    P.CB[m.from]=EMPTY;

    switch(m.to)
      {
      case A1: P.A.long_w=false;break;
      case H1: P.A.short_w=false;break;
      case A8: P.A.long_b=false;break;
      case H8: P.A.short_b=false;break;
      default: break;
      }
    P.A.eps_w=P.A.eps_b=OUT;
    P.A.to_move=(P.A.to_move==WHITE?BLACK:WHITE);//Flip the side ...

    switch(d.p1) // The piece which was moved.
      {
      case EMPTY: break;
      case WPAWN:
	if(m.to-m.from==2*n)   // Creates an en-passant square.
	  P.A.eps_w=m.from+n;
	else if(RANK(m.to)==n-1)// A promotion!
	  P.CB[m.to]=m.promote;
	else if(m.to!=m.from+n and d.p2==EMPTY) // An en passant capture.
	  {d.c3=m.to-n; d.p3=BPAWN; P.CB[d.c3]=EMPTY; }
	break;
      case WBISHOP:break;
      case WKNIGHT:break;
      case WROOK:
	if(m.from==A1) P.A.long_w=false;
	else if(m.from==H1) P.A.short_w=false;
	break;
      case WQUEEN: break;
      case WKING:
	P.A.long_w=P.A.short_w=false;// We cannot castle once king is moved.
	P.A.wk_pos=m.to;// Always update the position of the king.
	if(m.from==E1 and m.to==G1) { //SHORT CASTLE
	  P.A.castle_w=true;
	  d.c3=F1; d.p3=EMPTY; P.CB[F1]=WROOK;
	  d.c4=H1; d.p4=WROOK; P.CB[H1]=EMPTY;
	} else if(m.from==E1 and m.to==C1) { //LONG CASTLE
	  P.A.castle_w=true;
	  d.c3=D1; d.p3=EMPTY; P.CB[D1]=WROOK;
	  d.c4=A1; d.p4=WROOK; P.CB[A1]=EMPTY;
	}
	break;
      case BPAWN:
	if(m.from-m.to==2*n)// Creates an en-passant square
	  P.A.eps_b=m.from-n;
	else if(RANK(m.to)==0)// A promotion!
	  P.CB[m.to]=m.promote;		
	else if(m.to!=m.from-n and d.p2==EMPTY)// An en passant capture.
	  { d.c3=m.to+n; d.p3=WPAWN; P.CB[d.c3]=EMPTY;}
      case BBISHOP:break;	
      case BKNIGHT:break;
      case BROOK:
	if(m.from==A8) P.A.long_b=false;
	else if(m.from==H8) P.A.short_b=false;
	break;
      case BQUEEN:break;
      case BKING:
	P.A.long_b=P.A.short_b=false;//We cannot castle once king is moved.
	P.A.bk_pos=m.to;//Updating the position of the king.
	if(m.from==E8 and m.to==G8) { //SHORT castle
	  P.A.castle_b=true;
	  d.c3=F8; d.p3=EMPTY; P.CB[F8]=BROOK;
	  d.c4=H8; d.p4=BROOK; P.CB[H8]=EMPTY;
	} else if(m.from==E8 and m.to==C8) { //LONG castle
	  P.A.castle_b=true;
	  d.c3=D8; d.p3=EMPTY; P.CB[D8]=BROOK;
	  d.c4=A8; d.p4=BROOK; P.CB[A8]=EMPTY;
	}
      default:break;
      }
    history.push_back(d);
  }
  /// Undoes the last move.
  /**
   * The last move is undoed, and all the history is set accordingly.
   * Do not call this before the first move. The behaviour currently is
   * safe, but may be removed later for performace reasons.
   */
  void undo_move() {
    if(history.empty()) return;

    delta d=history.back();
    history.pop_back();
    ML.pop_back();

    P.A=d.A;
    P.CB[d.c1]=d.p1;
    P.CB[d.c2]=d.p2;
    if(d.c3!=OUT) P.CB[d.c3]=d.p3;
    if(d.c4!=OUT) P.CB[d.c4]=d.p4;
  }
  /// Checks whether the move m is valid.
  /**
   * Any crap is accepted as m, No side effects.
   * Unfortunately making it a const-function is difficult
   * I have to make the members `mutable' for the best performance,
   * or copy it temporarly some where and do something there, etc.
   * But all these are painfull. And I hope some reader will find
   * a better way to do it in a const environment.
   *
   * The difficulty comes from the part that it should not open
   * king to check, which can be verified easily only by making
   * that move and seeing if it actually opens and then undo that
   * move. Doing this is not possible with make_move and undo_move
   * functions as they are not const(not even logically).
   *
   * is_valid is a logically const function!!
   */
  bool is_valid(const move& m) /*const*/{
    move_list local;
    get_moves_of(m.from,local);

    if(std::find(local.begin(),local.end(),m)==local.end())
      return false;

    return not opens_king(m);
  }
  /// Gets a list of valid moves.
  /**
   * Assumes l is empty. If not the side effect is that the new set of moves
   * will get appended. A safe variant which clears it is under consideration.
   *
   * Suggestions are welcome.
   *
   * Similar to is_valid, valid_moves is logically a const function.
   *
   * It changes its argument instead of returning a container. This is for
   * efficiency purposes.(Obvious).
   */
  void get_moves(move_list & l) {
    for(cell c=0;c!=OUT;c++)
      get_moves_of(c,l);
    validate(l);
  }
  bool pinned(cell c) {
    move_list l;
    get_moves_of(c,l);
    if(l.empty()) return false;
    validate(l);
    if(l.empty()) return true;
    return false;
  }
  bool trapped(cell c) {
    colour cl=colour_of(P.CB[c]);
    if(cl==NONE) return false;
    cl=(cl==WHITE)?BLACK:WHITE;
    if(!under_threat(c, cl))
      return false;
      	
    move_list l;
    get_moves_of(c,l);
    validate(l);
    if(l.empty()) return true;

    move_list::iterator last=l.end();
    for(move_list::iterator it=l.begin();it!=last;++it) {
      //TODO try with faster approx alternates... any way this function will be used for heuristics only.
      make_move(*it);	
      if(!under_threat(it->to,cl)) {
        undo_move();
	return false;
      }
      undo_move();
    }
    return true;
  }

  friend std::ostream& operator << (std::ostream& os, const engine& e) {
    os<<"  a b c d e f g h\n\n";
    for(int r=n-1;r>=0;r--) {
      os<<r+1<<' ';
      for(int c=0;c<n;c++) {
	switch(e.P.CB[r*n+c]) {
	case EMPTY:os<<'.'; break;
	case WPAWN:os<<'P'; break;
	case WBISHOP:os<<'B'; break;
	case WKNIGHT:os<<'N'; break;
	case WROOK:os<<'R'; break;
	case WQUEEN:os<<'Q'; break;
	case WKING:os<<'K'; break;
	case BPAWN:os<<'p'; break;
	case BBISHOP:os<<'b'; break;
	case BKNIGHT:os<<'n'; break;
	case BROOK:os<<'r'; break;
	case BQUEEN:os<<'q';break;
	case BKING:os<<'k'; break;
	default: os <<"@";
	}
	os<<' ';
      }
      os<<r+1<<'\n';
    }
    os<<"\n  a b c d e f g h"<<std::endl;
    return os;
  }
};

#endif
